Practice Problems and Solutions 5 -- Dynamic vs Lexical Scope for Free (Global) variables.

You should do these problems on paper or mentally first, and only THEN check the solution.

Scope of non-local variables in Python and Java;

First we review how non-local variable references are resolved in Java.

NOTE: There will be no problems on Midterm 2 about Python or Java, but this is fundamental to understanding scope, and I suggest you go through them if you don't know how scope works.

5.1. Show what the following Java program prints out.

public class Main {

  static int n = 2;

  static int test(int k) {
    int n = 5;
    return n + k;
  }

  public static void main(String[] args) {
    int n = 10;
    System.out.println(n);
    System.out.println(test(n));
  }
}

Show Solution

  10
  15

5.2. Show what the following Java program prints out.

public class Main {

  static int n = 2;

  static int test(int k) {
    // int n = 5;                -- Note this line is commented out
    return n + k;
  }

  public static void main(String[] args) {
    int n = 10;
    System.out.println(n);
    System.out.println(test(n));
  }
}

Show Solution

  10
  12

5.3. Show what the following Java program prints out.

public class Main {

  static int n = 2;

  static int test(int k) {
    // int n = 5;                 Note that this line is commented out
    return n + k;
  }

  public static void main(String[] args) {
    // int n = 10;                Note that this line is commented out 
    System.out.println(n);
    System.out.println(test(n));
  }
}

Show Solution

  2
  4

5.4. Show what the following Java program prints out.

public class Main {

  static int n = 0;

  static int test(int k) {
    n = n + 1;                               
    return n + k;
  }

  public static void main(String[] args) {
    int n = 10;                              
    System.out.println(test(n));
    n = 100;
    System.out.println(test(n));
	n = 1000;
    System.out.println(test(n));
  }
}

Show Solution

  11
  102
  1003

5.5. Show what the following Java program prints out.

public class Main {

  static int n = 0;

  static int test(int k) {
    n = n + 1;                               
    return n + k;
  }

  public static void main(String[] args) {
    n = 10;                              
    System.out.println(test(n));
    int n = 100;
    System.out.println(test(n));
    n = 1000;
    System.out.println(test(n));
  }
}

Show Solution

  21
  112
  1013

Now a similar exercise in Python...

5.6. Show what the following Python program prints out.

n = 2

def test(k):
   n = 5
   return n + k

def main():
   n = 10
   print(n)
   print(test(n))

main()

Show Solution

  10
  15

5.7. What happens with the following Python program and why? (It attempts to simulate the Java program in 5.4.)

n = 0

def test(k):
   n = n + k
   return n + k

def main():
   n = 10
   print(test(n))
   n = 100
   print(test(n))
   n = 1000
   print(test(n))
main()

Show Solution

-----------------------------------------------------------------------
UnboundLocalError                     Traceback (most recent call last)
 in ()
     12    n = 1000
     13    print(test(n))
---> 14 main()
     15 

 in main()
      7 def main():
      8    n = 10
----> 9    print(test(n))
     10    n = 100
     11    print(test(n))

 in test(k)
      2 
      3 def test(k):
----> 4    n = n + k
      5    return n + k
      6 

UnboundLocalError: local variable 'n' referenced before assignment


Why: The variable n in the function test is a local variable, so its occurrence
on the right side of the assignment is unbound. 

5.8. How do we fix the problem in the previous problem so that it behaves as the Java program in 5.4?

Show Solution

We must declare the variable n to be global:

n = 0

def test(k):
   global n
   n = n + 1
   return n + k

def main():
   n = 10
   print(test(n))
   n = 100
   print(test(n))
   n = 1000
   print(test(n))
main()

It prints out the same:

  11
  102
  1003

For Midterm Two, I want you to know how dynamic vs lexical/static scoping works in Haskell, that is, what actually happens in Haskell, and what would happen if Haskell used dynamic scoping. There will be no questions about Python or Java, just Haskell examples, and just about what happens when you define functions and use those definitions. There will be nothing about the REPL's way of handling definitions, and the examples below use the REPL just for convenience; they might equally have been written in a file. The following exercises which show Haskell code are intended to illustrate the kinds of problems you might see on the exam. The Python questions are just for comparison (since I assume you know Python).

Non-Local Variables in Function Definitions in Python compared with Haskell

In problems 5.9 - 5.20, we show that with regard to the definitions made in the top level read-eval-print-loop, Python uses dynamic scoping and Haskell uses lexical scoping.

5.9. Show what the following Python code prints out.

n = 5

def test(k):
    return n + k

print(test(10))
    
n = 10

print(test(10))

Show Solution

  15
  20

5.10. Show what the following Haskell code prints out.

Prelude> n = 5

Prelude> test k = n + k

Prelude> test 10
15

Prelude> n = 10

Prelude> test 10
??

Show Solution

  15

Note: There is nothing special about using the REPL to do these kinds of examples, and the last example could just have easily been written in a file as:

ex5_10a = let    n = 5              in
          let    test k = n + k     in
                 test 10

ex5_10b = let    n = 5              in
          let    test k = n + k     in
          let    n = 10             in
                test 10

5.10b. What's the point of these last two problems?

Show Solution

Python uses dynamic scoping for non-local variables defined in its REPL, because it looked up and found the most
recent definition at the time when it was RUN; Haskell uses lexical/static scoping, so it bound n to the first 
value, found when the function was DEFINED. 

5.11. Show what the following Python code prints out.

n = 0

def test(k):
    n = 10
    def localTest(i):
        return n + k + i
    
    return localTest(10*k)

print(test(10))
    
n = 1000

print(test(10))

Show Solution

  120
  120

5.12. Show what the following Python code prints out.

n = 0

def test(k):
    #  n = 10                // this line commented out
    def localTest(i):
        return n + k + i
    
    return localTest(10*k)

print(test(10))
    
n = 1000

print(test(10))

Show Solution

  110
  1110

5.13. Show what the following Haskell code prints out.

Prelude> :set +m
Prelude> n = 0
Prelude> test k = let n = 10
Prelude|              localTest i = n + k + i
Prelude|          in (localTest 10)*k
Prelude> test 10
300
Prelude> n = 1000
Prelude> test 10
???

Show Solution

  300

5.14. Show what the following Haskell code prints out.

Prelude> n = 0
Prelude> test k = let localTest i = n + k + i
Prelude|          in (localTest 10)*k
Prelude> test 10
200
Prelude> n = 1000
Prelude> test 10
???

Show Solution

  200

5.15. Show what the following Haskell code prints out.

Prelude> n = 1
Prelude> g i = n + i
Prelude> f func k = func (10*k)
Prelude> f g 10
101
Prelude> n = 1000
Prelude> f g 10
???

Show Solution

  101

5.16. Show what the following Haskell code prints out.

Prelude> n = 1
Prelude> g i = n + i
Prelude> f func k = func (10*k)
Prelude> f g 10
101
Prelude> n = 1000
Prelude> f g 10
101
Prelude> f' func k = let n = 10 in func(10*k)
Prelude> f' g 10
???

Show Solution

  101

5.17. Show what the following Haskell code prints out.

Prelude> n = 1
Prelude> f = \x -> let k = n in x * k
Prelude> f 10
10
Prelude> n = 10
Prelude> f 10
??

Show Solution

  10

Now let's try the same thing in Python....

5.18. Show what the following Python code prints out. (= 5.15)

n = 1

def g(i):
    return n + i

def f(func,k):
    return func (10*k)

print(f(g,10))

n = 1000

print(f(g,10))

Show Solution

  101
  1100

5.19. Show what the following Python code prints out. (= 5.16)

n = 1

def g(i):
    return n + i

def f(func,k):
    return func (10*k)

print(f(g,10))

n = 1000

print(f(g,10))

def fPrime(func,k):
    return func(10*k)

print(fPrime(g,10))

Show Solution

  101
  1100
  1100

5.20. Show what the following Python code prints out. (= 5.17)

n = 1

def f(x):
    k = n
    return x * k

print(f(10))
n = 10
print(f(10))

Show Solution

  10
  100

In the remaining problems, we show that with regard to the definitions made locally (not in the REPL), both Python and Haskell use lexical scoping.

5.21. Show what the following Haskell code prints out and explain where the binding for n in the function h comes from.

Prelude> f func x = let n = 1 in func (x + n)

Prelude> g x = let n = 10 
Prelude|       in let h y = n + y 
Prelude|          in f h x

Prelude> g 0
??

Show Solution

  11
  
  The variable n comes from its lexical scope, therefore n = 10 in the function h and
  n = 1 in f, so we evaluate 10 + 0 + 1 = 11.  

5.22. What would be the value produced in the last problem if Haskell used dynamic scoping? Explain carefully.

Show Solution

It would produce 2, since when h was passed into f, it would be executed inside the (dynamic scope) of n = 1, 
so the result would be 1 + 0 + 1 = 2. 

5.23. What is the value printed by the following Python program and what does it say about the scope rules used for local variables (not defined in REPL) in Python?

def test (func,x):
    n = 2
    return func(x+n,x-n)

def tryIt(x,n):
    def why(x,y):
        return n * x + y
    return test(why,x)

print(tryIt(1,10))

Show Solution

29

Python uses LEXICAL scoping to find the binding for n when the function why is evaluated 
inside the context of the local binding for n inside test.  So it is as if the function
why is passed to try as (\x -> \y -> 10 * x + y) and the binding n = 2 is completely ignored, so:
tryIt(1,10) =>  test ((\x y -> 10 * x + y),1) 
            => (\x y -> 10 * x + y) (1+2) (1-2) 
			=> (\x y -> 10 * x + y) 3 (-1) 
			=> 10 * 3 + (-1) 
            => 29

5.24. What would be the value produced if Python used dynamic scoping in the last example? Where does the "free variable capture" take place?

Show Solution

Since the only issue is the binding for n, we would have

tryIt(1,10) => test(why,1)       -- the binding for n = 10 is lost
            => let n = 2 in why (1+n) (1-n)
            => let n = 2 in (\x y -> n*x+y) (1+n) (1-n)      -- free variable capture of n
            => (\x y -> 2*x+y) (1+2) (1-2)
			=> 2 * 3 + (-1)
			=> 5 			

5.25. Show what the following Haskell code prints out and explain where the binding for n in the function h comes from.

-- In the file test.hs

f :: (Integer -> Integer) -> Integer -> Integer
f g x = let n = 1 
        in g ((\n -> g (x + n)) 100)

test :: Integer -> Integer
test x = f g x
    where n = 3
          g = \x -> n + x
		  
		
Main> test 1000
????

Show Solution

  1106
  
  The variable n comes from its lexical scope, therefore n = 3 and g is a function that adds 
  3 to its argument in any context.  Therefore, 
  
      g ((\n -> g (1000 + n)) 100)
  =>  3 + ((\n -> g (1000 + n)) 100)
  =>  3 + (g (1000 + 100)))
  =>  3 + 3 + 1000 + 100
  =>  1106

5.26. What would be the value produced in the last problem if Haskell used dynamic scoping? Explain carefully.

Show Solution

Now the binding n = 3 is irrelevant, since n has bindings where g is dynamically called;
the easiest (though not very easy!) way to see the effect of dynamic binding is to turn everything
back into the lambda calculus (without closures) and evaluate:


      (\g -> \x -> ((\n -> g ((\n -> g (x + n)) 100)) 1)) (\x -> n + x) 1000
  =>  (\x -> ((\n -> (\x -> n + x) ((\n -> (\x -> n + x) (x + n)) 100)) 1))  1000
  =>  ((\n -> (\x -> n + x) ((\n -> (\x -> n + x) (1000 + n)) 100)) 1) 
  =>  ((\x -> 1 + x) ((\n -> (\x -> n + x) (1000 + n)) 100))
  =>  1 + ((\n -> (\x -> n + x) (1000 + n)) 100) 
  =>  1 + ((\x -> 100 + x) (1000 + 100))  
  =>  1 + (100 + 1000 + 100)  
  =>  1201
  
  Whew!!   So, isn't static binding easier to understand??

5.27. What is the value printed by the following Python program and what does it say about the scope rules used for local variables (not defined in REPL) in Python?

def f (func,x):
    n = 1
    return func(x+n)

def g(x):
    n = 10
    def h(y):
        return n + y
    return f(h,x)

print(g(0))

Show Solution

11

Python uses LEXICAL scoping to find the binding for n when the function h is evaluated inside the context of
the local binding for n inside f.  

5.28. What would be the value produced if Python used dynamic scoping to find the binding for the non-local variable n when h was evaluated inside the function f?

Show Solution

2

5.29. Does the following code cause an error in Python (i.e., before you call the function f)?

def g(func,x):
    n = 1
    return func(x+n)

def f(x):
    return n + x

Show Solution

Nope!

5.30. Does the following code cause an error in Python (i.e., AFTER you call the function f)?

def g(func,x):
    n = 1
    return func(x+n)

def f(x):
    return n + x
	
print(g(f,0))

Show Solution

YES.  The following error is reported ONLY AFTER you call the function:

-----------------------------------------------------------------------
NameError                             Traceback (most recent call last)
 in ()
      6     return n + x
      7 
----> 8 print(g(f,0))

 in g(func, x)
      1 def g(func,x):
      2     n = 1
----> 3     return func(x+n)
      4 
      5 def f(x):

 in f(x)
      4 
      5 def f(x):
----> 6     return n + x
      7 
      8 print(g(f,0))

NameError: name 'n' is not defined

5.31. Does the following code cause an error in Haskell (i.e., before you call the function f)?

def g(func,x):
    n = 1
    return func(x+n)

def f(x):
    return n + x

Show Solution

Yup!

:32:7: error: Variable not in scope: n

5.32. What accounts for the differing behavior in Haskell and Python as shown in the last three problems?

Show Solution

Haskell does (mostly) static type checking on all code, even before it is executed; Python does (mostly) dynamic type checking,
and finds errors when it runs into them during execution.